Within a typical digital communications system, information is represented as a sequence of binary bits (e.g., ones and zeros). To transmit the information, the binary bits are modulated onto an analogue signal waveform, and transmitted over a communications channel. The communications channel may introduce noise and interference that can corrupt the transmitted signal. At the receiver, the corrupted received signal is mapped back into the digital domain, although bit errors may result due to the introduced noise.
To compensate for bit errors, channel coding is often used in digital communications systems to allow for error detection and correction to occur. Channel coding is often accomplished by selectively introducing redundant bits into the transmitted bit stream. These redundant bits allow detection and correction of bit errors in a received bit stream.
One type of channel code includes convolutional codes. Convolutional codes are one of the most widely used channel codes in practical communications systems. The ratio between the number of input bits and the number of output bits is called the code rate. For instance, a convolutional coder which calculates two output bits for each input bit is typically referred to as a half-rate convolutional coder. Similarly, a convolutional coder which calculates three output bits for each input bit is typically referred to as a one-third-rate convolutional coder.
When a bit stream is convolutional coded, the communicating entities may each employ a decoder that implements a Viterbi algorithm. The Viterbi algorithm is one of the most resource-consuming algorithms for decoding a convolutional coded bit stream, but the Viterbi algorithm does provide the statistical maximum likelihood decoding. Such maximum likelihood decoding is especially valuable when signal quality is low.